#include "btree.hpp"

#include <iostream>
#include <string>
#include <stack>
#include <queue>
using namespace std;
using node = struct node;

Tree::Tree()
{
    root = nullptr;
}

Tree::Tree(int root_val)
{
    root = new node(root_val);
}

Tree::~Tree()
{
    if (root)
    {
        delete root;
    }
    cout << "destroy tree" << endl;
}

const node *Tree::getRoot()
{
    return this->root;
}

bool Tree::add(int val)
{
    node *cur = this->root;

    if (!this->root)
    {
        this->root = new node(val);
        cout << "add val " << val << " success!" << endl;
        return true;
    }

    while (true)
    {
        if (cur->val == val)
        {
            cout << "add val " << val << " failed!" << endl;
            return false;
        }
        else if (cur->val > val && cur->lchild)
        {
            cur = cur->lchild;
        }
        else if (cur->val < val && cur->rchild)
        {
            cur = cur->rchild;
        }
        else if (cur->val > val && !cur->lchild)
        {
            cur->lchild = new node(val);
            break;
        }
        else if (cur->val < val && !cur->rchild)
        {
            cur->rchild = new node(val);
            break;
        }
    }
    cout << "add val " << val << " success!" << endl;
    return true;
}

bool Tree::del(int val)
{
    if(!this->root)
    {
        return false;
    }
    node* prev = nullptr;
    node* cur = this->root;
    while(cur)
    {
        if(cur->val > val)
        {
            prev = cur;
            cur = cur->lchild;
        }
        else if(cur->val < val)
        {
            prev = cur;
            cur = cur->rchild;
        }
        else 
        {
            break;
        }
    }
    if(!cur)    //此时如果cur为nullptr 则未找到
    {
        return false;
    }

    // 此时cur指向被删除元素 并且做右子树都存在
    if(cur->lchild && cur->rchild)
    {
        node* rmin = cur->rchild;
        node* rprev = cur;
        while(rmin->lchild)
        {
            rprev = rmin;
            rmin = rmin->lchild;
        } 
        // 此时rmin指向被删除元素右子树的最小元素
        cur->val = rmin->val;
        prev = rprev;
        cur = rmin;
    }

    node* child = cur->lchild ? cur->lchild : cur->rchild;

    if(!prev) 
    {
        this->root = child;
    }

    node* tmp = cur;
    tmp->val = val;     // 对于删除行为无意义 只是让打印数字正确
    if(prev->lchild == cur)
    {
        prev->lchild = child;
        delete tmp;
    }
    else if(prev->rchild == cur)
    {
        prev->rchild = child;
        delete tmp;
    }

    return true;

}

// tree travel recursion
void Tree::preOrder_r(const node *root)
{
    if (root)
    {
        cout << root->val << " ";
        preOrder_r(root->lchild);
        preOrder_r(root->rchild);
    }
}

void Tree::inOrder_r(const node *root)
{
    if (root)
    {
        inOrder_r(root->lchild);
        cout << root->val << " ";
        inOrder_r(root->rchild);
    }
}

void Tree::postOrder_r(const node *root)
{
    if (root)
    {
        postOrder_r(root->lchild);
        postOrder_r(root->rchild);
        cout << root->val << " ";
    }
}

// tree travel
void Tree::preOrder()
{
    if (!this->root)
        return;
    stack<node *> s;
    node *p = this->root;
    s.push(p);
    while (!s.empty())
    {
        p = s.top();
        s.pop();
        cout << p->val << " ";
        if (p->rchild)
        {
            s.push(p->rchild);
        }
        if (p->lchild)
        {
            s.push(p->lchild);
        }
    }
    cout << endl;
}

void Tree::inOrder()
{
    if (!this->root)
        return;
    stack<node *> s;
    node *p = this->root;
    while (p || !s.empty())
    {
        while (p)
        {
            s.push(p);
            p = p->lchild;
        }
        p = s.top();
        s.pop();
        cout << p->val << " ";
        p = p->rchild;
    }
    cout << endl;
}

void Tree::postOrder()
{
    if (!this->root)
        return;
    stack<node *> s1;
    stack<node *> s2;
    node *p = this->root;
    s1.push(p);
    while (!s1.empty())
    {
        p = s1.top();
        s1.pop();
        s2.push(p);
        if (p->lchild)
        {
            s1.push(p->lchild);
        }
        if (p->rchild)
        {
            s1.push(p->rchild);
        }
    }
    while (!s2.empty())
    {
        p = s2.top();
        s2.pop();
        cout << p->val << " ";
    }
    cout << endl;
}

void Tree::levelOrder()
{
    if (!this->root)
        return;
    queue<node *> q;
    node *p = this->root;
    q.push(p);
    cout << "level order: ";
    while (!q.empty())
    {
        p = q.front();
        q.pop();
        cout << p->val << " ";
        if (p->lchild)
        {
            q.push(p->lchild);
        }
        if (p->rchild)
        {
            q.push(p->rchild);
        }
    }
    cout << endl;
}
